package leetcode_1_200;

import javax.jws.Oneway;
import java.util.HashMap;
import java.util.Map;

public class LeeCode_106 {
    public static void main(String[] args) {
//        TreeNode treeNode = buildTree(new int[]{9, 3, 15, 20, 7}, new int[]{9, 15, 7, 20,3});
//        TreeNode treeNode = buildTree(new int[]{-1}, new int[]{-1});
        TreeNode treeNode = buildTree(new int[]{3,2,1}, new int[]{3,2,1});
    }

    private static TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> imap = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++)
            imap.put(inorder[i], i);
        return f(inorder, postorder, imap, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    private static TreeNode f(int[] inorder, int[] postorder, Map<Integer, Integer> imap, int s, int e, int s2, int e2){
        if (s > e)
            return null;
        if (s == e)
            return new TreeNode(inorder[s]);
        int rn = postorder[e2];
        e2--;
        int i = imap.get(rn);
        int lc = i - s;
        int rc = e - i;
        TreeNode l = f(inorder, postorder, imap, s, i - 1, s2, s2 + lc - 1);
        TreeNode r = f(inorder, postorder, imap, i + 1, e, e2 - rc + 1, e2);
        return new TreeNode(rn, l, r);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
